Queue

What is Queue? Queue is easier to understand compared to Stack, we see queues all the time in real world scenarios, like Queue of people for a movie or a bank. Generally it is a First Come First Serve, you aren't going to let in the movie house the last person that arrives right. 

• First Come First Serve in the Computer Science world is also known as FIFO (First In First Out)

Key Methods

• Add - Inserts element to the last of the queue
• Poll/Remove - Gets the first element from the Queue
• Peek - Checks the first value of the queue, but does not remove it

Key Variables

Below are generally what the Queue internally keeps track of (not specifically called these names)

• Rear - where is the last of the Queue, this is were we insert the value
• Front - Here is where we take the values when processing/polling
• Size - number of elements there are

Say you have a queue of customers, waiting to see the Bank Teller

**Bank Teller<- \[Old Lady, Young Man, Engineer, Banker, Late College Kid\]**

                        ^ Front                                                                   ^Rear

As per above, once a new customer comes in, he's not going to cut in line to the front of the Old Lady (well if he decent guy that is), but generally new entries comes in the the last of the Queue, so any new person coming in goes after the rear which in this example is the Late College Kid

For the Bank Tellers point view, He needs to know the front to see who is next in line for transacting with. Which in this case is the old lady.

Example Implementation

Below is an example implementation of a Queue, this is only for simplicity sake, generally you would use a built-in Queue from your programming language, that handles any ArrayIndexOutOfBounds and is more safe to use than your own implementation.

package algorithm.datastructures;  
  
public class Queue {  
    private static int rear \= -1, front \=0, size\=0;  
 private String\[\] data;  
  
 public Queue(int size){  
        data \= new String\[size\];  
 }  
  
    public void insert(String value){  
        data\[++rear\] = value;  
 size++;  
 }  
  
    public String remove(){  
        size\--;  
 return data\[front++\];  
 }  
  
    public String peekFront(){  
        return data\[front\];  
 }  
    public String peekRear(){  
        return data\[rear\];  
 }  
  
    public static void main(String\[\] args){  
        Queue customers = new Queue(5);  
         customers.insert("Old Lady");  
         customers.insert("Young Man");  
         customers.insert("Engineer");  
         customers.insert("Banker");  
         System.out.println("Next Customer to be procaessed : " \+ customers.remove());  
         System.out.println("Next Customer to be processed : " \+ customers.remove());  
         customers.insert("Late College Kid");  
         System.out.println("Next in line is: "\+ customers.peekFront());  
         System.out.println("Last in line is: "\+ customers.peekRear());  
         System.out.println("Next Customer to be processed : " \+ customers.remove());  
         System.out.println("Next Customer to be processed : " \+ customers.remove());  
         System.out.println("Next Customer to be processed : " \+ customers.remove());  
         }  
}

Circular Queue

Is where when you exceed the Queue, you insert AND overwrite the first of the Queue. So in this case the Rich CEO Man comes in and the Bank Teller can only accommodate 5 in the Queue at a time

**Bank Teller<- \[Old Lady, Young Man, Engineer, Banker, Late College Kid\]  <- Rich CEO Man**

                        ^ Front                                                                   ^Rear

**Bank Teller<- \[Rich CEO Man, Young Man, Engineer, Banker, Late College Kid\]** 

                        ^ Front                                                                   ^Rear

Obviously this is not a good example and since we are not using a Linked List, the Old Lady is kicked off the Queue altogether! Linked List will be covered in a different topic.

Circular Queue is very unique in nature, and does not always apply to all scenarios, a good example us of it might be an Airport Baggage Carousel